package _1_初级._1_2_集合;

import java.util.Stack;

public class _20_有效的括号 {

    /**
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
     *
     * 有效字符串需满足：
     *
     * 左括号必须用相同类型的右括号闭合。
     * 左括号必须以正确的顺序闭合。
     * 注意空字符串可被认为是有效字符串。
     *
     * 示例 1:
     *
     * 输入: "()"
     * 输出: true
     * 示例 2:
     *
     * 输入: "()[]{}"
     * 输出: true
     * 示例 3:
     *
     * 输入: "(]"
     * 输出: false
     * 示例 4:
     *
     * 输入: "([)]"
     * 输出: false
     * 示例 5:
     *
     * 输入: "{[]}"
     * 输出: true
     *
     */

    //方法一：
    public static boolean isValid(String s) {

        char[] chars = s.toCharArray();

        Stack<Character> stack = new Stack<>();
        char c;

        for (char aChar : chars) {
            c = aChar;
            if (c == '(' || c == '{' || c == '[') {
                stack.push(aChar);
            } else {
                if (c == '}') {
                    if (stack.peek() == '{') {
                        stack.pop();
                    } else {
                        return false;
                    }
                } else if (c == ']') {
                    if (stack.peek() == '[') {
                        stack.pop();
                    } else {
                        return false;
                    }
                } else if (c == ')') {
                    if (stack.peek() == '(') {
                        stack.pop();
                    } else {
                        return false;
                    }
                }
            }
        }

        return stack.empty();
    }




    public static void main(String[] args) {

        String s1 = "(((((())))))";
        String s2 = "()()()()";
        String s3 = "(((((((()";
        String s4 = "((()(())))";
        String s6 = "()";
        String s7 = "()[]{}";
        String s8 = "([)]";
        String s9 = "{[]}";

        System.out.println("(((((()))))) : " + isValid(s1));
        System.out.println("()()()() : " + isValid(s2));
        System.out.println("(((((((() : " + isValid(s3));
        System.out.println("((()(()))) : " + isValid(s4));
        System.out.println("() : " + isValid(s6));
        System.out.println("()[]{} : " + isValid(s7));
        System.out.println("([)] : " + isValid(s8));
        System.out.println("{[]} : " + isValid(s9));
    }

}
